package com.fang.algorithm.sort.selection;

import java.util.Arrays;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 选择排序 单个元素与剩余所有元素比较
 * @date 2022/1/5 2:48 下午
 **/
public class Test01_Selection {

    public static void main(String[] args) {
        int[] arr = new int[]{10, 20, 49, 99, 23, 22, 11, 60};
//        selectionSort01(arr);
//        selectionSort02(arr);
        selectionSort03(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void selectionSort03(int[] arr) {
        // 二元选择排序
        int minIndex, maxIndex;
        // i 只需要遍历一半
        for (int i = 0; i < arr.length / 2; i++) {
            minIndex = i;
            maxIndex = i;
            for (int j = i + 1; j < arr.length - i; j++) {
                if (arr[minIndex] > arr[j]) {
                    // 记录最小值的下标
                    minIndex = j;
                }
                if (arr[maxIndex] < arr[j]) {
                    // 记录最大值的下标
                    maxIndex = j;
                }
            }
            // 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
            if (minIndex == maxIndex) {
                break;
            }
            // 将最小元素交换至首位
            arrSwap(arr, i, minIndex);
            // 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
            if (maxIndex == i) {
                maxIndex = minIndex;
            }
            // 将最大元素交换至末尾
            int lastIndex = arr.length - 1 - i;
            arrSwap(arr, maxIndex, lastIndex);
        }
    }

    private static void selectionSort02(int[] arr) {
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            arrSwap(arr, i, minIndex);
        }
    }

    private static void selectionSort01(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    arrSwap(arr, i, j);
                }
            }
        }
    }

    private static void arrSwap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
